package com.kehao.newcoder;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class NC102Solution {

    private static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

    private TreeNode t1,t2;
    private Map<TreeNode,TreeNode> childParentMap= new HashMap<>();

    private void dfs(TreeNode node,int o1,int o2){
        if(node.val == o1) t1 = node;
        if(node.val == o2) t2 = node;
        if(node.left!=null){
            childParentMap.put(node.left,node);
            dfs(node.left,o1,o2);
        }
        if(node.right!=null){
            childParentMap.put(node.right,node);
            dfs(node.right,o1,o2);
        }
    }

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        dfs(root,o1,o2);
        Set<TreeNode> visitedSet = new HashSet<>();
        while (t1!=root){
            visitedSet.add(t1);
            t1 = childParentMap.get(t1);
        }
        while (t2!=null){
            if(visitedSet.contains(t2)){
                return t2.val;
            }else {
                t2 = childParentMap.get(t2);
            }
        }
        return root.val;
    }
}
